#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bag {
    int v;
    int w;
    int cnt;
};
bool cmp(bag a, bag b) {
    return a.w<b.w;
}
int main() {
    int n,m;
    cin>>n>>m;
    int* dp=new int[m+1];
    int* res=new int[m+1];
    int cnt[m+1];
    bag b[n];
    for (int i=0; i<n; i++) {
        scanf("%d%d%d", &b[i].w, &b[i].v, &b[i].cnt);
    }
//    sort(b, b+n, cmp);
    for (int i=0; i<m+1; i++) {
        dp[i]=0;
        res[i]=0;
    }
    for (int i=0; i<n; i++) {
        memset(cnt, 0, sizeof(cnt));
        for (int j=0; j<m+1; j++) {
            if(j-b[i].w>=0 && res[j-b[i].w]+b[i].v>dp[j] && res[j-b[i].w]+b[i].v>dp[j-b[i].w]+b[i].v && cnt[j-b[i].w]<b[i].cnt) {
                res[j]=res[j-b[i].w]+b[i].v;
                cnt[j]=cnt[j-b[i].w]+1;
            }
            else if (j-b[i].w>=0 && dp[j-b[i].w]+b[i].v>dp[j]) {
                res[j]=dp[j-b[i].w]+b[i].v;
                cnt[j]++;
            }
            else res[j]=dp[j];
            if (j>0 && res[j-1]>res[j]) {
                res[j]=res[j-1];
                cnt[j]=cnt[j-1];
            }
        }
        swap(res,dp);
        cout<<"dp: ";
        for (int k=0; k<m+1; k++) cout<<dp[k]<<' ';
        cout<<endl;
        cout<<"cnt:";
        for (int k=0; k<m+1; k++) cout<<cnt[k]<<' ';
        cout<<endl;
    }
    cout<<dp[m]<<endl;
    delete [] res;
    delete [] dp;
    return 0;
}
